const UnionFind = require('../dataStruct/unionFind').UnionFind;

/**
 * 图（以边为处理对象）
 * 
 * @author shuyuan.dai 2021-02-05
 */
class Graph {
    constructor() {
        // 每个点指向的最后一条边
        this.head = [];
        // 每个边的同源节点的上一个边
        this.parent = [];
        // 每一条边指向的点
        this.V = [];
        // 边的数量
        this.cnt = 0;
        // 流量
        this.streams = [];
    }

    /**
     * Prim 最小生成树算法
     * 
     * @returns 最小生成树
     */
    generateMST() {
        let validEdges = [];
        for(let i=0; i < this.head.length; ++i) {
            let u = this.head[i];
            while(u >= 0) {
                validEdges.push({
                    start: i,
                    end: this.V[u],
                    weight: this.streams[u]
                })
                u = this.parent[u];
            }
        }
        validEdges.sort((a, b) => a.weight - b.weight);
        
        let unionFind = new UnionFind(validEdges.length), 
            graph = new Graph();
        for(let i=0; i < validEdges.length; ++i) {
            if(!unionFind.connected(validEdges[i].start, validEdges[i].end)) {
                unionFind.union(validEdges[i].start, validEdges[i].end);
                graph.addEdge(validEdges[i].start, validEdges[i].end, validEdges[i].weight);
            }
        }
        return graph;
    }

    /**
     * 添加一条边
     * 
     * @param {*} v1 源节点
     * @param {*} v2 目标节点
     * @param {*} stream 流量
     */
    addEdge(v1, v2, stream) {
        if(v1 < 0 || v2 < 0 || stream < 0) {
            return false;
        }

        for(let start=Math.min(v1, v2), last = Math.max(v1, v2); start <= last; ++start) {
            this.head[start] = this.head[start] >= 0? this.head[start]: -1;
        }

        this.parent[this.cnt] = this.head[v1];
        this.head[v1] = this.cnt;
        this.streams[this.cnt] = stream;
        this.V[this.cnt] = v2;
        this.cnt += 2;
        return true;
    }

    /**
     * 自动计算源点
     */
    calSourcePoint() {
        let sourceIndex = [];
        for(let i=0; i < this.head.length; ++i) {
            let hasJoinIn = false;
            for(let j=0; j < this.V.length; ++j) {
                if(this.V[j] == i) {
                    hasJoinIn = true;
                    break;
                }
            }
            // 没有入度只有出度
            if(!hasJoinIn && this.head[i] > 0) {
                sourceIndex.push(i);
            }
        }
        return sourceIndex;
    }

    /**
     * 自动计算汇点
     */
    calMeetingPoint() {
        let targetIndex = [];
        for(let i=0; i < this.head.length; ++i) {
            let hasJoinIn = false;
            for(let j=0; j < this.V.length; ++j) {
                if(this.V[j] == i) {
                    hasJoinIn = true;
                    break;
                }
            }
            // 有入度没有出度
            if(hasJoinIn && this.head[i] < 0) {
                targetIndex.push(i);
            }
        }
        return targetIndex;
    }
}

exports.Graph = Graph;